/*
Copyright (c) 2009-2010, Warwick Warp Limited
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above copyright
      notice, this list of conditions and the following disclaimer in the
      documentation and/or other materials provided with the distribution.
    * Neither the name of the Warwick Warp Limited nor the
      names of its contributors may be used to endorse or promote products
      derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL WARWICK WARP LIMITED BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#ifndef WARRAY_WARRAY_EXTENTS_H_INCLUDED
#define WARRAY_WARRAY_EXTENTS_H_INCLUDED

#include <boost/static_assert.hpp>
#include <algorithm>
#include <numeric>
#include <iostream>
#include "warray_types.h"

namespace warp {
namespace detail {
template<typename T,detail::warray_types::size_type NUM_DIMS>
class index_gen
{
public:
	typedef detail::warray_types::size_type  size_type;
	typedef detail::warray_types::index_type index_type;
	typedef const T* const_iterator;
	typedef       T*       iterator;
	
	explicit index_gen()
	{
		std::fill(m_indices,m_indices+NUM_DIMS,0);
	}
	
	const_iterator begin() const
	{
		return m_indices;
	}
	
	const_iterator end() const
	{
		return m_indices+NUM_DIMS;
	}
	
	iterator begin()
	{
		return m_indices;
	}
	
	iterator end()
	{
		return m_indices+NUM_DIMS;
	}
	
protected:
	explicit index_gen(const index_gen<T,NUM_DIMS-1>& lhs, const T& rhs)
	{
		std::copy(lhs.begin(),lhs.end(),m_indices);
		m_indices[NUM_DIMS-1] = rhs;
	}
	explicit index_gen(const_iterator source)
	{
		std::copy(source,source+NUM_DIMS,m_indices);
	}
	
	T m_indices[NUM_DIMS];
};

template<typename T>
class index_gen<T,0>
{
public:
	typedef detail::warray_types::size_type  size_type;
	typedef detail::warray_types::index_type index_type;
	typedef const T* const_iterator;
	typedef       T*       iterator;
	
	index_gen() 
	{
	}
	
	const_iterator begin() const
	{ 
		return NULL; 
	}
	
	const_iterator end() const
	{ 
		return NULL; 
	}
	
	iterator begin()
	{ 
		return NULL; 
	}
	
	iterator end()
	{ 
		return NULL; 
	}

protected:
	explicit index_gen(const_iterator source)
	{
	}
};

} // namespace detail

/*!
	\brief Index dimensions using a TNT/traditional 1-based indexing scheme
	
	TNT arrays refer to dimensions as dim1, dim2, dim3 etc., however, for 
	consistency with the C-language we store and index the dimensions array 
	using 0-based indexing. In order to make code more readable the following 
	enumeration is provided to index up to 11 dimensions in a more verbose 
	fashion.
*/
enum dim_index_e
{
	dim1 = 0,
	dim2 = 1,
	dim3 = 2,
	dim4 = 3,
	dim5 = 4,
	dim6 = 5,
	dim7 = 6,
	dim8 = 7,
	dim9 = 8,
	dim10 = 9,
	dim11 = 10
};

/*!
	\brief Store array indices for N-dimensional arrays
	
	Generate array indices using warp::indices, for example index i,j with
	\code
	array_indices<2> ij = warp::indices[i][j]
	\endcode
*/
template<detail::warray_types::size_type NUM_DIMS>
class array_indices : 
	public detail::index_gen<detail::warray_types::index_type,NUM_DIMS>
{
	typedef detail::index_gen<detail::warray_types::index_type,NUM_DIMS> super_type;
public:
	typedef typename super_type::size_type      size_type;
	typedef typename super_type::index_type     index_type;
	typedef typename super_type::const_iterator const_iterator;

	//! \brief Create a array of zero indices
	explicit array_indices()
	{
	}

	/*! 
		\brief Index a new dimension
		
		The new dimension is the leading, or fastest varying, dimension.
	*/
	array_indices<NUM_DIMS+1> operator[](index_type dim) const
	{
		return array_indices<NUM_DIMS+1>(*this,dim);
	}
	
	/*! 
		\brief Determine the index of the ith dimension
		
		i is the zero-based index of the dimension
	*/
	index_type index(index_type i) const
	{
		return super_type::begin()[i];
	}
	
	index_type& index(index_type i)
	{
		return super_type::begin()[i];
	}
	
	/*!
		\brief Get the N fastest varying indices
	*/
	template<size_type N>
	array_indices<N> slice() const
	{
		BOOST_STATIC_ASSERT(N<=NUM_DIMS);
		return array_indices<N>(super_type::begin()+NUM_DIMS-N);
	}
	
protected:
	explicit array_indices(const array_indices<NUM_DIMS-1>& lhs, index_type i) :
		super_type(lhs,i)
	{
	}
	explicit array_indices(const_iterator source) :
		super_type(source)
	{
	}
	
	template<size_type OD>
	friend class array_indices;
};

/*!
	\brief Store array extents for N-dimensional arrays
	
	Generate array dimensions using warp::extents, for example an n by m 
	two dimensional set of extents can be generated with
	\code
	array_extents<2> dims = warp::extents[n][m]
	\endcode
*/
template<detail::warray_types::size_type NUM_DIMS>
class array_extents : 
	public detail::index_gen<detail::warray_types::size_type,NUM_DIMS>
{
	typedef detail::index_gen<detail::warray_types::size_type,NUM_DIMS> super_type;
public:
	typedef typename super_type::size_type      size_type;
	typedef typename super_type::index_type     index_type;
	typedef typename super_type::const_iterator const_iterator;
	typedef typename super_type::iterator       iterator;

	//! \brief Create a array of zero indices
	explicit array_extents()
	{
	}

	/*! 
		\brief Index a new dimension
		
		The new dimension is the leading, or fastest varying, dimension.
	*/
	array_extents<NUM_DIMS+1> operator[](size_type i) const
	{
		return array_extents<NUM_DIMS+1>(*this,i);
	}
	
	/*! 
		\brief Determine the size of the ith dimension
		
		i is the zero-based index of the dimension
	*/
	size_type dim(index_type i) const
	{
		return super_type::begin()[i];
	}
	
	size_type& dim(index_type i)
	{
		return super_type::begin()[i];
	}
	
	/*!
		\brief Get the N fastest varying indices
	*/
	template<size_type N>
	array_extents<N> slice() const
	{
		BOOST_STATIC_ASSERT(N<=NUM_DIMS);
		return array_extents<N>(super_type::begin()+NUM_DIMS-N);
	}
	
	array_extents<NUM_DIMS-1> slice_one() const
	{
		BOOST_STATIC_ASSERT(1<=NUM_DIMS);
		return array_extents<NUM_DIMS-1>(super_type::begin()+1);
	}
	
	size_type product() const
	{
		return std::accumulate(super_type::begin(),super_type::end(),1,std::multiplies<size_type>());
	}
	
	bool operator==(const array_extents<NUM_DIMS>& r) const
	{
		return std::equal(super_type::begin(),super_type::end(),r.begin());
	}
	
	bool operator!=(const array_extents<NUM_DIMS>& r) const
	{
		return !std::equal(super_type::begin(),super_type::end(),r.begin());
	}
	
protected:
	explicit array_extents(const array_extents<NUM_DIMS-1>& lhs, size_type rhs) :
		super_type(lhs,rhs)
	{
	}
	explicit array_extents(const_iterator source) :
		super_type(source)
	{
	}
	
	template<size_type OD>
	friend class array_extents;
};

/*!
	\brief Store strides for N-dimensional arrays
*/
template<detail::warray_types::size_type NUM_DIMS>
class array_strides
{
public:
	typedef detail::warray_types::size_type size_type;
	typedef detail::warray_types::index_type index_type;
	typedef const size_type *const_iterator;

	//! \brief Create an empty set of strides
	explicit array_strides()
	{
		std::fill(m_strides,m_strides+NUM_DIMS,0);
	}

	//! \brief Compute the strides for a contiguous array of the specified size
	explicit array_strides(const array_extents<NUM_DIMS>& extents)
	{
		m_strides[int(NUM_DIMS-1)] = 1;
		for(int i=int(NUM_DIMS-2);i>=0;--i)
			m_strides[i] = m_strides[i+1]*extents.dim(i+1);
	}
	
	/*!
		\brief Get the stride for the ith dimension
		
		i is a zero based index.
	*/
	size_type stride(index_type i) const
	{
		return m_strides[i];
	}
	
	//! \brief Determine the number of dimensions
	size_type num_dims() const
	{
		return NUM_DIMS;
	}
	
	//! \brief Iterate over the strides of each dimension
	const_iterator begin() const 
	{
		return m_strides;
	}
	
	//! \brief Iterate over the strides of each dimension
	const_iterator end() const
	{
		return m_strides+NUM_DIMS;
	}
	
	/*!
		\brief Get the N fastest varying indices
	*/
	template<size_type N>
	array_strides<N> slice() const
	{
		BOOST_STATIC_ASSERT(N<=NUM_DIMS);
		return array_strides<N>(begin()+NUM_DIMS-N);
	}
	
	//! \brief Compare two sets of strides
	bool operator==(const array_strides<NUM_DIMS>& r) const
	{
		return std::equal(begin(),end(),r.begin());
	}
	
	//! \brief Compare two sets of strides
	bool operator!=(const array_strides<NUM_DIMS>& r) const
	{
		return !std::equal(begin(),end(),r.begin());
	}
	
protected:
	explicit array_strides(const_iterator it)
	{
		std::copy(it,it+NUM_DIMS,m_strides);
	}
	
	size_type m_strides[NUM_DIMS];
	
	template<size_type ON>
	friend class array_strides;
};

//! \brief Determine if an array with the given extents and strides is contiguous
template<detail::warray_types::size_type NUM_DIMS>
bool contiguous(const array_extents<NUM_DIMS>& extents, const array_strides<NUM_DIMS>& strides)
{
	if(strides.stride(NUM_DIMS-1) != 1)
		return false;
	for(int i=NUM_DIMS-2;i>=0;--i)
		if(strides.stride(i) != strides.stride(i+1)*extents.dim(i+1))
			return false;
	return true;
}

namespace {
//! \brief Scoped global variable for generating n-dimensional extents
array_extents<0> extents;
array_indices<0> indices;
}

template <typename T,size_t N>
std::ostream& operator<<(std::ostream &s, const detail::index_gen<T,N> &e)
{
	for(typename detail::index_gen<T,N>::const_iterator it=e.begin();it!=e.end();++it)
		s << "[" << *it << "]";
	return s;
}

template <size_t N>
std::ostream& operator<<(std::ostream &s, const array_strides<N> &e)
{
	for(typename array_strides<N>::const_iterator it=e.begin();it!=e.end();++it)
		s << "[" << *it << "]";
	return s;
}

} // namespace warp

#endif
